package C043;

import java.util.Scanner;

/**
 * ClassName: C01
 * Package: C043
 * Description: 打怪兽问题
 *
 * @Author BCXJ
 * @Create 2025/2/6 20:32
 * @Version 1.0
 * @Since 1.0
 */
public class C01 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int T = scan.nextInt();
        for (int i = 0; i < T; i++) {
            int n = scan.nextInt();
            int m = scan.nextInt();
            int[][] arr = new int[n][2];
            for (int j = 0; j < n; j++) {
                arr[j][0] = scan.nextInt();
                arr[j][1] = scan.nextInt();
            }
            int ans = process(arr, 0, m);
            System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);// n 个技能，m的血量的怪物
        }
    }

    // i当前来到第几个技能，怪物剩余的血量
    private static int process(int[][] arr, int i, int m) {
        if(m <= 0) {
            return i;
        }

        if(i == arr.length) {
            return Integer.MAX_VALUE;
        }
        int ans = Integer.MAX_VALUE;
        for (int j = i; j < arr.length; j++) {
            swap(arr, i, j);
            ans = Math.min(ans, process(arr, i + 1, m <= arr[i][1] ? m - 2 * arr[i][0] : m - arr[i][0]));
            swap(arr, i, j);
        }
        return ans;
    }

    private static void swap(int[][] arr, int i, int j) {
        int temp = arr[i][0];
        arr[i][0] = arr[j][0];
        arr[j][0] = temp;
        temp = arr[i][1];
        arr[i][1] = arr[j][1];
        arr[j][1] = temp;
    }


}
